package player;

import list.ArrayList;
import board.Board;
import board.DepthFirstSearch;
import board.Piece;

//import test.Printer;

public class Minimax2 {

	static final double DEPTH_DECAY = .995;
	static final int MAX_SCORE_WHITE = 1000;
	static final int MAX_SCORE_BLACK = -1000;

	/*
	 * static HashMap<Board, Integer> hash = getHashMap();//new HashMap<Board,
	 * Integer>(2000, .3f); static int totalEvalTime = 0; static int cacheHit =
	 * 0; static int cacheMiss = 0;
	 */

	/** 
	 * Chooses the best STEP or ADD move based on the current condition of the board
	 * 
	 * @param b
	 * @param color
	 * @param depth
	 *            # plies to look ahead
	 * @return the "best" move for the player given a board.
	 */
	public static Move chooseMove(Board b, int color, int depth) {
		// Printer.set(false);
		if (color == Piece.WHITE && b.stepTimeWhite()) {
			return getStepMoveWhite(b, depth);
		} else if (color == Piece.BLACK && b.stepTimeBlack()) {
			return getStepMoveBlack(b, depth);
		} else {
			return getAddMove(b, color, depth);
		}
	}
	/** 
	 * Chooses the best STEP move for WHITE based on the current condition of the board
	 * 
	 * @param b
	 * @param depth
	 *            # plies to look ahead
	 * @return the "best" Step move for the WHITE player given a board and depth
	 */
	private static Move getStepMoveWhite(Board b, int depth) {
		ArrayList<Piece> pieces = b.getWhitePieces();
		Move bestMove = null;
		Piece bestOldPiece = null;
		int maxScore = MAX_SCORE_BLACK;
		for (int i = 0; i < pieces.size(); i++) {
			Piece oldpiece = pieces.get(i);
			b.clearSpot(oldpiece.xpos, oldpiece.ypos);
			for (int y = 0; y < b.getLength(); y++) {
				for (int x = 0; x < b.getLength(); x++) {
					if (x == oldpiece.xpos && y == oldpiece.ypos) {
						continue;
					}
					Move move = new Move(x, y);
					if (b.isLegal(move, Piece.WHITE) ) {
						b.makeMove(move, Piece.WHITE);
						int value = minimaxWhite(b, depth-1, maxScore, true);
						b.clearSpot(x, y);
						if (value > maxScore) {
							maxScore = value;
							bestMove = move;
							bestOldPiece = oldpiece;
						}
					}
				}
			}
			b.makeMove(new Move(oldpiece.xpos, oldpiece.ypos), Piece.WHITE);
		}
		return new Move(bestMove.x1, bestMove.y1, bestOldPiece.xpos,
				bestOldPiece.ypos);
	}
	/** 
	 * Chooses the best STEP move for BLACK based on the current condition of the board
	 * 
	 * @param b
	 * @param depth
	 *            # plies to look ahead
	 * @return the "best" Step move for the BLACK player given a board and depth
	 */
	private static Move getStepMoveBlack(Board b, int depth) {
		ArrayList<Piece> pieces = b.getBlackPieces();
		Move bestMove = null;
		Piece bestOldPiece = null;
		int maxScore = MAX_SCORE_WHITE;
		for (int i = 0; i < pieces.size(); i++) {
			Piece oldpiece = pieces.get(i);
			b.clearSpot(oldpiece.xpos, oldpiece.ypos);
			for (int y = 0; y < b.getLength(); y++) {
				for (int x = 0; x < b.getLength(); x++) {
					if (x == oldpiece.xpos && y == oldpiece.ypos) {
						continue;
					}
					Move move = new Move(x, y);
					if (b.isLegal(move, Piece.BLACK)) {
						b.makeMove(move, Piece.BLACK);
						int value = minimaxBlack(b, depth-1, maxScore, true);
						b.clearSpot(x, y);
						if (value < maxScore) {
							maxScore = value;
							bestMove = move;
							bestOldPiece = oldpiece;
						}
					}
				}
			}
			b.makeMove(new Move(oldpiece.xpos, oldpiece.ypos), Piece.BLACK);
		}
		return new Move(bestMove.x1, bestMove.y1, bestOldPiece.xpos,
				bestOldPiece.ypos);
	}
	/** 
	 * Chooses the best ADD move based on the current condition of the board
	 * 
	 * @param b
	 * @param color
	 * @param depth
	 *            # plies to look ahead
	 * @return the "best" Step move for the player given a board, depth, and player color
	 */
	private static Move getAddMove(Board b, int color, int depth) {
		Move m = null;;
		if (color == Piece.WHITE) {
			int maxScore = MAX_SCORE_BLACK;
			for (int y = 0; y < b.getLength(); y++) {
				for (int x = 0; x < b.getLength(); x++) {
					Move move = new Move(x, y);

					if (b.isLegal(move, Piece.WHITE)) {
						// Printer.println("WHITE Analyzing move:" + move);
						// Printer.tab();
						b.makeMove(move, Piece.WHITE);
						int value = minimaxWhite(b, depth-1, maxScore, false);
						b.clearSpot(x, y);
						if (value > maxScore) {
							// Printer.untab();
							// Printer.println("new max score!:" +
							// value+" @ move:"+move);
							// Printer.tab();
							// pause();
							maxScore = value;
							m = move;
						}
						// Printer.untab();
					}

				}
			}
			// hash.clear();
			return m;
		} else {
			//long start = System.currentTimeMillis();
			int minScore = MAX_SCORE_WHITE;
			for (int y = 0; y < b.getLength(); y++) {
				for (int x = 0; x < b.getLength(); x++) {
					Move move = new Move(x, y);
					if (b.isLegal(move, Piece.BLACK)) {
						b.makeMove(move, Piece.BLACK);
						int value = minimaxBlack(b, depth - 1, minScore, false);
						b.clearSpot(x, y);
						if (value < minScore) {
							minScore = value;
							m = move;
						}
					}
				}
			}
			/*
			 * System.out.println("Move summary:");
			 * System.out.println("\tmove score: "+minScore);
			 * System.out.println(
			 * "\tTotal thinking time:"+(System.currentTimeMillis()-start));
			 * System.out.println("\ttotalEvalTime: "+totalEvalTime);
			 * System.out.println("\tcacheHit: "+cacheHit);
			 * System.out.println("\tcacheMiss (# evals): "+cacheMiss);
			 * System.out.printf("\thit rate: %.2f%s \n",100*((double)cacheHit/
			 * (cacheHit+cacheMiss)), "%"); totalEvalTime = 0; cacheHit = 0;
			 * cacheMiss =0 ; hash.clear();
			 */
			return m;
		}
	}
	/** 
	 * Chooses the best ADD move based on the current condition of the board
	 * 
	 * @param b
	 * @param color
	 * @param depth
	 *            # plies to look ahead
	 * @beta the "best" score black can get
	 * @step whether the move is a step or add move
	 * @return the "best" score based on the current board
	 */
	private static int minimaxWhite(Board b, int depth, int beta, boolean step) {
		// Printer.println("WHITE Depth: "+depth);
		// pause();

		if (depth <= 0) {
			int i = eval(b);
			return i;
		}
		if (DepthFirstSearch.hasWin(Piece.WHITE, b) != null) {
			return MAX_SCORE_WHITE;
		}
		int min = MAX_SCORE_WHITE; // black tries to minimize this score
		ArrayList<Piece> pieces = b.getBlackPieces();
		Piece oldpiece = null;
		for (int i = 0; i < pieces.size(); i++) {
			if(!step) {
				i = pieces.size();
			}
			else {
				oldpiece = pieces.get(i);
				b.clearSpot(oldpiece.xpos, oldpiece.ypos);
			}
			for (int y = 0; y < b.getLength(); y++) {
				for (int x = 0; x < b.getLength(); x++) {
					Move m = new Move(x, y);
					if(step) {
						if (x == oldpiece.xpos && y == oldpiece.ypos) {
							continue;
						}
						m = new Move(x, y, oldpiece.xpos, oldpiece.ypos);
					}
					if (b.isLegal(m, Piece.BLACK)) {
						// Printer.println("BLACK Analyzing move:" + m);
						// Printer.tab();
						b.makeMove(m, Piece.BLACK);
						int value = minimaxBlack(b, depth - 1, min, step);
						b.clearSpot(x, y);
	
						if (value < beta) { //do not evaluate any other moves, simply return value right now.
							return value;
						}
	
						if (value < min) {
							// Printer.println("new min score!:" + value);
							min = value;
						}
						// Printer.untab();
					}
	
				}
			}
			if(step){
				b.makeMove(new Move(oldpiece.xpos, oldpiece.ypos), oldpiece.color);
			}
		}
		return (int) (DEPTH_DECAY * min);
	}
	/** 
	 * Chooses the best ADD move based on the current condition of the board
	 * 
	 * @param b
	 * @param color
	 * @param depth
	 *            # plies to look ahead
	 * @alpha the "best" score white can get
	 * @step whether the move is a step or add move
	 * @return the "best" score based on the current board
	 */
	private static int minimaxBlack(Board b, int depth, int alpha, boolean step) {
		// Printer.println("BLACK Depth: "+depth);
		
		if (depth <= 0) {
			int i = eval(b);
			return i;
		}
		if (DepthFirstSearch.hasWin(Piece.BLACK, b) != null) {
			return MAX_SCORE_BLACK;
		}
		int max = MAX_SCORE_BLACK; // white tries to maximize this score
		ArrayList<Piece> pieces = b.getWhitePieces();
		Piece oldpiece = null;
		for (int i = 0; i < pieces.size(); i++) {
			if(!step) {
				i = pieces.size();
			}
			else {
				oldpiece = pieces.get(i);
				b.clearSpot(oldpiece.xpos, oldpiece.ypos);
			}
			for (int y = 0; y < b.getLength(); y++) {
				for (int x = 0; x < b.getLength(); x++) {
					Move m = new Move(x, y);
					if(step) {
						if (x == oldpiece.xpos && y == oldpiece.ypos) {
							continue;
						}
						m = new Move(x, y, oldpiece.xpos, oldpiece.ypos);
					}
					if (b.isLegal(m, Piece.WHITE)) {
						// Printer.println("WHITE Analyzing move:" + m);
						// Printer.tab();
						b.makeMove(m, Piece.WHITE);
						int value = minimaxWhite(b, depth - 1, max, step);
						b.clearSpot(x, y);
						if (value > alpha) {  //do not evaluate any other moves, simply return value right now.
							return value;
						}
						if (value > max) {
							// Printer.println("new max score!:" + value);
							max = value;
						}
						// Printer.untab();
					}
				}
			}
			if (step) {
				b.makeMove(new Move(oldpiece.xpos, oldpiece.ypos), oldpiece.color);
			}
		}
			/*for (int y = 0; y < b.getLength(); y++) {
				for (int x = 0; x < b.getLength(); x++) {
					Move m = new Move(x, y);
					if (b.isLegal(m, Piece.WHITE)) {
						// Printer.println("WHITE Analyzing move:" + m);
						// Printer.tab();
						b.makeMove(m, Piece.WHITE);
						int value = minimaxWhite(b, depth - 1, max, step);
						b.clearSpot(x, y);
						if (value > beta) {  //do not evaluate any other moves, simply return value right now.
							return value;
						}
						if (value > max) {
							// Printer.println("new max score!:" + value);
							max = value;
						}
						// Printer.untab();
					}
				}
			}*/
		return (int) (DEPTH_DECAY * max);
	}

	/**
	 * Eval the board to return an integer between -1000 (black advantage) and
	 * 1000 (white advantage)
	 * 
	 * @param b
	 * @return the score given to the board
	 */
	public static int eval(Board b) {
		/*
		 * long start = System.currentTimeMillis(); Integer val = hash.get(b);
		 * if( val!=null){ cacheHit++; return val; } cacheMiss++;
		 */
		if (DepthFirstSearch.hasWin(Piece.BLACK, b) != null)
			return -1000;
		if (DepthFirstSearch.hasWin(Piece.WHITE, b) != null)
			return 1000;

		ArrayList<Integer> bList = DepthFirstSearch.getNetworkLengths(b,
				Piece.BLACK);
		ArrayList<Integer> wList = DepthFirstSearch.getNetworkLengths(b,
				Piece.WHITE);
		int bScore = 0, wScore = 0;
		if (bList == null || wList == null)
			return 0;
		for (int x = 0; x < bList.size(); x++) {
			bScore += 1 + bList.get(x) * bList.get(x);
		}
		for (int x = 0; x < wList.size(); x++) {
			wScore += 1 + wList.get(x) * wList.get(x);
		}

		wScore = (int) (2000 * ((double) wScore / (bScore + wScore))) - 1000;
		/*
		 * hash.put(b, wScore); totalEvalTime+=
		 * System.currentTimeMillis()-start;
		 */
		return wScore;
	}

}
